1913E - Matrix Problem - CodeForces Solution

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define Hagry ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector <pair<int, int>>;
using vvi = vector <vector<int>>;

const int OO = 1e9 + 5;
const int N = 2e5 + 5;

struct Edge {
    int to;
    ll cost;
    int cap, flow, backEdge;
};

struct MCMF
{

    const int inf = 1000000010;
    int n;
    vector<vector<Edge>> g;

    MCMF(int _n) {
        n = _n + 1;
        g.resize(n);
    }

    void addEdge(int u, int v, int cap, ll cost) {
        Edge e1 = {v, cost, cap, 0, (int) g[v].size()};
        Edge e2 = {u, -cost, 0, 0, (int) g[u].size()};
        g[u].push_back(e1);
        g[v].push_back(e2);
    }

    pair<ll, int> minCostMaxFlow(int s, int t) {
        int flow = 0;
        ll cost = 0;
        vector<int> state(n), from(n), from_edge(n);
        vector<ll> d(n);
        deque<int> q;
        while (true) {
            for (int i = 0; i < n; i++)
                state[i] = 2, d[i] = OO, from[i] = -1;
            state[s] = 1;
            q.clear();
            q.push_back(s);
            d[s] = 0;
            while (!q.empty()) {
                int v = q.front();
                q.pop_front();
                state[v] = 0;
                for (int i = 0; i < (int) g[v].size(); i++) {
                    Edge e = g[v][i];
                    if (e.flow >= e.cap || (d[e.to] <= d[v] + e.cost))
                        continue;
                    int to = e.to;
                    d[to] = d[v] + e.cost;
                    from[to] = v;
                    from_edge[to] = i;
                    if (state[to] == 1) continue;
                    if (!state[to] || (!q.empty() && d[q.front()] > d[to]))
                        q.push_front(to);
                    else q.push_back(to);
                    state[to] = 1;
                }
            }
            if (d[t] == OO) break;
            int it = t, addflow = inf;
            while (it != s) {
                addflow = min(addflow,
                              g[from[it]][from_edge[it]].cap
                              - g[from[it]][from_edge[it]].flow);
                it = from[it];
            }
            it = t;
            while (it != s) {
                g[from[it]][from_edge[it]].flow += addflow;
                g[it][g[from[it]][from_edge[it]].backEdge].flow -= addflow;
                cost += g[from[it]][from_edge[it]].cost * addflow;
                it = from[it];
            }
            flow += addflow;
        }
        return {cost, flow};
    }
};

void TC(){
    int n, m;
    cin >> n >> m;

    int src = 0, sink = n + m + 1, sum = 0;
    MCMF mcmf(sink+1);
    int val;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cin >> val;
            sum += val;
            mcmf.addEdge(i, n+j,1,val == 0);
        }
    }

    int sumRows = 0, sumCols = 0;
    for(int i=1; i<=n; ++i){
        cin >> val;
        sumRows += val;
        mcmf.addEdge(src, i, val, 0);
    }
    for(int i=1; i<=m; ++i){
        cin >> val;
        sumCols += val;
        mcmf.addEdge(n+i, sink, val, 0);
    }

    pair<ll, int> ans = mcmf.minCostMaxFlow(src, sink);
    if(sumRows == sumCols && ans.second == sumRows){
        cout << 2*ans.first + sum - ans.second;
    }
    else
        cout << -1;
}

int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#endif
    Hagry
    int t = 1;
//    cin >> t;
    while (t--) {
        TC();
        cout << '\n';
    }
    return 0;
}